import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/17 18:31
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.countPalindromicSubsequence("bbcbaba");
    }
    public int countPalindromicSubsequence(String s) {
        Set<String> set = new HashSet<>();
        int n = s.length();
        int[] left = new int[26];
        int[] right = new int[26];
        for (int i = 0; i < n; i++) {
            right[s.charAt(i) - 'a']++;
        }
        left[s.charAt(0)-'a']++;
        right[s.charAt(0)-'a']--;
        for (int i = 1; i < n-1; i++) {
            int index = s.charAt(i)-'a';
            right[index]--;
            for (int j = 0; j < 26; j++) {
                if (left[j] >= 1 && right[j] >= 1) {
                    char same = (char) (j + 'a');
                    set.add("" + same + s.charAt(i) + same);
                }
            }
            left[index]++;
        }
        return set.size();
    }
}
